// 给定一个二叉树，返回所有从根节点到叶子节点的路径。

// 思路1：前序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function binaryTreePaths(root) {
    let result = []
    function dfs(root, curPath) {
        if (!root.left && !root.right) {
            result.push(curPath + root.val)
            return
        }
        curPath += root.val + '->'
        if (root.left) {
            dfs(root.left, curPath)
        }
        if (root.right) {
            dfs(root.right, curPath)
        }
    }
    dfs(root, '')
    return result
}

// 思路2，迭代,先序
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，stack的大小
function binaryTreePaths2(root) {
    if (!root) {
        return []
    }
    let stack = [root]
    let pathStack = ['']
    let result = []
    while (stack.length) {
        let node = stack.pop()
        let path = pathStack.pop()
        if (!node.left && !node.right) {
            result.push(path + node.val)
            continue
        }
        path += node.val + '->'
        if (node.right) {
            stack.push(node.right)
            pathStack.push(path)
        }
        if (node.left) {
            stack.push(node.left)
            pathStack.push(path)
        }
    }
    return result
}


const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(binaryTreePaths(root))
console.log(binaryTreePaths2(root))